Not every task that a user seeks to have performed by a computing device can be efficiently performed by that user's personal computing device. Instead, collections of powerful, multi-processor computing devices can provide greater processing capabilities, thereby enabling users to perform tasks that could not efficiently be performed by their personal computing devices, without having to themselves purchase such costly computing hardware. Typically, groups of users share such collections of computing devices such that each user can have access to the collection of computing devices to perform complex and time-consuming data processing. The more users' data processing that can be accommodated by a collection of computing devices, the more value can be realized from such a collection. Consequently, it is desirable to utilize as much of the data processing capability of a collection of computing devices as possible without negatively impacting those users who seek to utilize such collection of computing devices to perform data processing.
Unfortunately, scheduling the processing of users' tasks across multiple computing devices is often not straightforward. For example, some data processing requested by users involves the reading or writing of large quantities of data that may not be able to be efficiently performed if the data processing is being performed by a computing device that is remote from the computer readable storage medium on which such data is to be read from or to be written to. As another example, the data processing requested by users can typically be broken down into individual jobs and processes that can be scheduled individually. If delays are introduced between the performance of one process and the performance of the subsequent process then, over the course of performing a single task, the accumulated delay can quickly become unacceptably large. As yet another example, to provide users with a minimum threshold of service, each user can be guaranteed a certain amount of data processing capability that can be provided by the collection of computing devices. In many cases, however, not every user of the collection of computing devices will be simultaneously utilizing their guaranteed data processing capability. Consequently, in those instances, much of the data processing capabilities of the collection of computing devices can remain unutilized, resulting in underutilization of the overall system, and the attendant inefficiencies that such underutilization introduces. However, were the available processing capability distributed to those users currently desiring it, then it may not be available for other users to whom it was guaranteed.
For small collections of computing devices, the scheduling of processes to be executed by those computing devices can be solved through known mathematical strategies for solving flow graphs. More specifically, each process to be executed can be modeled as a node, or “vertex” in a flow graph, as can each computing device on which such a process could be executed. However, as will be recognized by those skilled in the art, the complexity of such flow graphs, and the efficiency with which they can be solved, is proportional to the number of edges in the flow graph, where each connection between a vertex is an “edge”. Thus, for example, were a process agnostic as to the computing device on which it was executed, an edge would exist from such a process to each computing device. The complexity of such a flow graph could, theoretically, be as high as the number of processes to be scheduled multiplied by the number of computing devices on which such processes could be executed. As can be seen, such a flow graph can quickly become too complex to be solved efficiently as the number of computing devices and the number of processes to be scheduled increases beyond a few dozen. Consequently, such an approach is not practical for modern data processing computer clusters that can comprise thousands of computing devices.